4 Нахождение максимального потока и определение минимального разреза
Для поиска максимального потока и минимального разреза в сети существует
алгоритм Форда-Фалкерсона (Ford-Fulkerson algorithm). Этот алгоритм является одним из
первых алгоритмов решения данной задачи, но, несмотря на это, считается достаточно
эффективным. Для наглядности разобьём его на два алгоритма: алгоритм нахождения
максимального потока и алгоритм нахождения минимального разреза. Рассмотрим их.
4.1 Алгоритм нахождения максимального потока
Определение 4.1. Аугментальная цепь (дополняющая цепь, увеличивающая цепь)
– это цепь, соединяющая s и t, такая, что для каждой дуги
«прямого» направления
(ориентированной в направлении от s к t)
, а для каждой дуги
,
ориентированной в «обратном» направлении (от t к s),
.
Иными словами, если дуга цепи имеет «прямое» направление, нам важна
возможность повышения величины её потока. И наоборот, если дуга цепи имеет
«обратное» направление, нам важна возможность уменьшения величины её потока.
Ниже приводим описание алгоритма нахождения максимального потока.
Алгоритм нахождения максимального потока. Алгоритм начинает работу с
произвольного допустимого потока (например, нулевого), затем величина его
увеличивается с помощью систематического поиска всевозможных аугментальных цепей
от s к t. Для этого вершинам сети приписываются метки, указывающие, вдоль каких дуг и
на сколько может быть увеличен поток. Как только такая цепь находится, поток вдоль неё
увеличивается до максимального значения, все пометки в вершинах стираются, и вновь
полученный поток берётся в качестве исходного, и так до тех пор, пока такие потоки
можно построить.
Пусть
– текущая вершина,
– предыдущая вершина. Тогда вершине
приписывается пометка следующего вида:
или
, где
–
означает, что поток допускает увеличение вдоль дуги
;
– означает, что поток
допускает уменьшение вдоль дуги
.
– максимальная величина
дополнительного потока, который может проходить от s к
.
В первом приближении алгоритм может выглядеть следующим образом:
1. Задать сети произвольный допустимый поток (например, нулевой);
2. Найти аугментальную цепь, соединяющую s и t. Если такой нет, перейти к шагу 5;